package dp_package.p01;

import java.util.Arrays;

/**
 * 416. 分割等和子集输入：nums = [1,5,11,5]
 * 输出：true
 * 解释：数组可以分割成 [1, 5, 5,11] 和 [11] 。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-04 20:16
 */
public class L416 {
    //    public boolean canPartition(int[] nums) {
//        Arrays.sort(nums);
//        int sum = Arrays.stream(nums).sum();
//        if(sum%2==1) return false;//和为奇数无法分割
//
//        int sum1 = 0;
//        int left = 0;
//        int right = 0;
//        while (right < nums.length) {
//            if (sum1 == sum / 2) {
//                return true;
//            } else if (sum1 < sum / 2) {
//                sum1 += nums[right++];
//            } else {
//                sum1 -= nums[left++];
//            }
////            right++;
//        }
//        return false;
//    }
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if((sum&1)== 1) return false;
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length][target + 1];
        dp[0][0] = true;
        //初始化第一行
        if(nums[0]<=target){
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                }else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length - 1][target];
    }

    public static void main(String[] args) {
        L416 l416 = new L416();
        boolean b = l416.canPartition(new int[]{14, 9, 8, 4, 3, 2});
        System.out.println(b);
    }
}
